﻿#ifndef _DLINNKLIST_H
#define _DLINNKLIST_H

#include <stdlib.h>
#include <string.h>

#ifdef __cplusplus
extern "C" {
#include "memorypool.h"
}
#endif

typedef struct _tag_DLinkListNode* LPDLinkListNode;
typedef struct _tag_DLinkListNode
{
	LPDLinkListNode	pre;	//父节点
	LPDLinkListNode	next;	//子节点
	void* data;	//节点值
	unsigned int	key;	//键值
}DLinkListNode;

typedef struct _tag_DLinkListNodeHead
{
	LPDLinkListNode	top;			//首节点
	LPDLinkListNode	tail;			//尾节点
	LPDLinkListNode	cur;			//当前节点
	unsigned int	length;			//节点数

}DLinkListNodeHead;

enum INSER_TYPE { INSERT_PRE, INSERT_NEXT };

class DLinkList
{
private:
	MemoryPool* m_heap;
	unsigned int m_max;
	DLinkListNodeHead	m_head;
public:
	DLinkList(unsigned int max);
	~DLinkList();

	bool	Insert(void* data, unsigned int key, INSER_TYPE type = INSERT_NEXT);
	void	Delete();
	void	Delete(void* node);
	void	Clean();
	void	Seek(void* node);
	bool	Seek_pre();
	bool	Seek_next();
	void	Seek_top();
	void	Seek_tail();
	void* Get_data();
	unsigned int	Get_key();
	void* Get_node();
	unsigned int	Get_length();
};

//	构造函数
DLinkList::DLinkList(unsigned int max)
{
	m_max = max;
	m_heap = MemoryPoolInit(m_max * sizeof(DLinkListNode) * 3, m_max * sizeof(DLinkListNode) * 2);
	m_head.top = NULL;
	m_head.tail = NULL;
	m_head.cur = NULL;
	m_head.length = 0;
}

//	析构函数
DLinkList::~DLinkList()
{
	if (m_heap)
	{
		MemoryPoolClear(m_heap);
		MemoryPoolDestroy(m_heap);
	}
}

bool DLinkList::Insert(void* data, unsigned int key, INSER_TYPE type)
{
	LPDLinkListNode node = (LPDLinkListNode)MemoryPoolAlloc(m_heap, sizeof(DLinkListNode));

	if (!node) {
		return false;
	}

	node->data = data;
	node->key = key;

	//	将当前节点的父与子链接起来
	if (m_head.cur)
	{
		if (type == INSERT_NEXT)
		{
			node->pre = m_head.cur;
			node->next = m_head.cur->next;
			m_head.cur->next = node;
			if (node->next)
				node->next->pre = node;
			if (m_head.cur == m_head.tail)
				m_head.tail = node;
		}
		else
		{
			node->pre = m_head.cur->pre;
			node->next = m_head.cur;
			m_head.cur->pre = node;
			if (node->pre)
				node->pre->next = node;
			if (m_head.cur == m_head.top)
				m_head.top = node;
		}
	}
	else
	{
		//	链表是空的
		node->pre = NULL;
		node->next = NULL;
		m_head.top = node;
		m_head.tail = node;
	}

	m_head.cur = node;

	m_head.length++;

	return true;
}

void DLinkList::Delete()
{
	if (!m_head.cur)
		return;

	LPDLinkListNode cur = m_head.cur;

	if (--m_head.length == 0)
	{
		m_head.top = NULL;
		m_head.tail = NULL;
		m_head.cur = NULL;
	}
	else
	{
		//	将当前节点的父与子链接起来
		if (cur->pre)
			cur->pre->next = cur->next;

		if (cur->next)
		{
			cur->next->pre = cur->pre;
			//	更新表头
			m_head.cur = cur->next;
		}
		else
		{
			m_head.cur = cur->pre;
		}

		if (cur == m_head.top)
			m_head.top = cur->next;
		else if (cur == m_head.tail)
			m_head.tail = cur->pre;
	}

	MemoryPoolFree(m_heap, cur);
}

void DLinkList::Delete(void* node)
{
	Seek(node);
	Delete();
}

void DLinkList::Clean()
{
	memset(m_heap, 0, m_max * sizeof(DLinkListNode));
	m_head.top = NULL;
	m_head.tail = NULL;
	m_head.cur = NULL;
	m_head.length = 0;
	MemoryPoolClear(m_heap);
}

void DLinkList::Seek(void* node)
{
	m_head.cur = (LPDLinkListNode)node;
}

bool DLinkList::Seek_pre()
{
	if (m_head.cur)
	{
		if (m_head.cur->pre)
		{
			m_head.cur = m_head.cur->pre;
			return true;
		}
	}

	return false;
}

bool DLinkList::Seek_next()
{
	if (m_head.cur)
	{
		if (m_head.cur->next)
		{
			m_head.cur = m_head.cur->next;
			return true;
		}
	}

	return false;
}

void DLinkList::Seek_top()
{
	m_head.cur = m_head.top;
}

void DLinkList::Seek_tail()
{
	m_head.cur = m_head.tail;
}

void* DLinkList::Get_data()
{
	return m_head.cur ? m_head.cur->data : NULL;
}

unsigned int DLinkList::Get_key()
{
	return m_head.cur ? m_head.cur->key : 0;
}

void* DLinkList::Get_node()
{
	return m_head.cur;
}

unsigned int DLinkList::Get_length()
{
	return m_head.length;
}

#endif
